#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
typedef long long LL;

LL t, k;
LL f[N][N], g[N][N];

void init()
{
	for(int i = 0;i <= 2000;i ++)
	{
		f[i][0] = 1;
		for(int j = 1;j <= i;j ++)
		{
			f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % k;
			g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] + (f[i][j] == 0 ? 1 : 0);
		}
		g[i][i + 1] = g[i][i];
	}
}

int main()
{
	cin >> t >> k;
	init();
	while(t --)
	{
		LL n, m; cin >> n >> m;
		cout << g[n][min(m, n)] << endl;
	}
	return 0;
}